Proof of Work

到目前為止我們把交易紀錄連成一條鏈了，整個鏈上的交易向後追蹤就不可能重複交易，在一條完整的鏈中重複交易問題終於解決了，但是下一個區塊(block)該如何被加到鏈中呢?

我們在Day2 51%攻擊中說過，比特幣論文中假設算力大的那一方是正常運作的，所以應該讓算力大的那一方來決定哪些交易將被加到鏈中的下一個區塊。於是便引入了工作量證明(Proof of Work)的概念，給出一個計算很耗時的問題，先算完的那方才可以告訴所有人哪一個區塊能被加入鏈中，這個耗時可能花費的時間跟算力基本是成正比，而且這個問題雖然計算答案很花時間，可是驗證計算的答案對不對卻很簡單，如同我們在Day3舉的兩個質數相乘的例子。

繼續用到Proof of Work章節的圖示:

還記得我們昨天範例程式中預留的prev_Hash跟nonce兩個欄位嗎?prev_Hash跟Day3的數位簽章產生的簽名功能很像，不過在這裡是使用SHA256來做hash function，而Day3的數位簽章目的是為了驗證交易者的身份不被破解，在此使用SHA256做hash則是要讓區塊鏈由算力多者主導。

Proof of Work的運作方式就是一直去猜nonce的值，猜到下一個區塊的prev_Hash有若干個0開頭(required zero bits)，這個區塊就是能合法加入鏈中的下一個區塊，由於區塊的timestamp也被hash進下一個區塊一直傳下去，不只無法重複交易，區塊的產生順序也可以被確保。

而這個猜的命中率是與算力掛勾的，前面說過密碼學技術中良好的hash fucntion具有雪崩效應(Avalanche Effect)​的性質，有可能出現的hash值也是均勻分佈的，要生出下一個合法的區塊只能靠猜，對電腦來說就是把所有的數字都填進nonce try上一遍，

新增Proof of Work的部份，並在廣播時驗證:

# 將區塊昭告天下
def broadcast(new_block):

    # trace block看裡面的transaction跟前面的能不能對上
    # 不過後面的章節才會講到實際的transaction中的內容
    # 我們先假設一個transaction的內容只能跟之後的交易一次
    # 第i個node的第j的區塊的第k個transaction
    for i in range(len(nodes)):

        # 先確定區塊的合法性
        # 才能確定區塊是不是算力大的一方來的
        if new_block['timestamp'] < blockchain[-1]['timestamp']:
            print("node %d:區塊不合法，應按照時間生成" % i)
            continue

        if new_block['pre_Hash'] != hashlib.sha256(str(blockchain[-1])).hexdigest():
            print("node %d:區塊不合法，前一個hash值對不起來" % i)
            continue

        if hashlib.sha256(str(new_block)).hexdigest()[0:4] != '0000':
            print("node %d:區塊不合法，hash值不符合proof of work的規定" % i)
            continue

        check_legel = True
        for j in range(len(nodes[i])):
            for k in range(len(nodes[i][j]['Txs'])):
                for l in range(len(new_block['Txs'])):
                    if nodes[i][j]['Txs'][k]['preowner_vk'] == new_block['Txs'][l]['preowner_vk']:
                        check_legel = False
        if check_legel == True:
            nodes[i].append(new_block)
            print("node %d:紀錄了新block中的所有交易" % i)
        else:
            print("node %d:抱歉，這筆交易不合規定，不能重複交易" % i)

# try到適合的Nonce來讓該區塊合法
def proof_of_work(blockchain, block):

    # 區塊的產生時間應該按照順序
    if block['timestamp'] < blockchain[-1]['timestamp']:
        print('區塊不合法')
        return None

    block['pre_Hash'] = hashlib.sha256(str(blockchain[-1])).hexdigest()
    # 這裡都當作required zero有32bits
    # required zero只是論文中為了說明概念使用
    # 真正的難度在現實應用中會根據前一個block的計算時間之類的動態調整
    # 實際應用上是要讓hsah小於某個值才算合法 不然真的都用required zero難度只能一次調2的次方
    while True:
        block['nonce'] = random.randint(-214783648, 2147483647)
        if hashlib.sha256(str(block)).hexdigest()[0:4] == '0000':
            print(hashlib.sha256(str(block)).hexdigest())
            print('計算合法區塊成功')
            return block

延續一下昨天的小明、小華範例，用個多執行緒來模擬一下算力:

# 小華
owner2_sk = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)
owner2_vk = owner2_sk.get_verifying_key()

transaction2 = trade(blockchain[0]['Txs'][0], '1000萬拿去收好', owner1_sk, owner2_vk)
block1 = add_tran(transaction2)


# 小明黨羽(也可能是小明自導自演)
owner_other_sk = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)
owner_other_vk = owner_other_sk.get_verifying_key()

transaction_other = trade(blockchain[0]['Txs'][0], '同一個1000萬拿去收好', owner1_sk, owner_other_vk)
block1_other = add_tran(transaction_other)

lock = threading.Lock()
done = False
def thread_pow(block_unpow):
    global done
    block_pow = proof_of_work(blockchain, copy.copy(block_unpow))
    if block_pow != None:
        lock.acquire()
        # 為了簡化流程
        # 這裡有人開始廣播其他算完的執行緒就停了
        if done != True:          
            done = True
            broadcast(block_pow)
        lock.release()


threads = []
for i in range(9):
    threads.append(threading.Thread(target=thread_pow, args = (block1,)))
    
threads.append(threading.Thread(target=thread_pow, args = (block1_other,)))
    
for t in threads:
    t.start()

time.sleep(10)
'''
可以看到前面是四個bytes是0開頭
0000af27c7b9b4e186b0b7a4707df0d07abc2914f1cc85c2323436a2e548e172
計算合法區塊成功
node 0:紀錄了新block中的所有交易
node 1:紀錄了新block中的所有交易
node 2:紀錄了新block中的所有交易
node 3:紀錄了新block中的所有交易
.....

'''

print(owner2_vk.to_pem())
'''
-----BEGIN PUBLIC KEY-----
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEbDNA4hzQN7iTbnHXvXaHsAxBk9AAOgfd
5j5/KF7dwVK7NsaMSLl1V7EYPWSvGr2P84pGT6UNFTYSLVKodeI+KA==
-----END PUBLIC KEY-----

'''

print(owner_other_vk.to_pem())
'''
-----BEGIN PUBLIC KEY-----
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEVM203oPz+Gab6jsWrMCQGTM1947TUY/1
xbYOdu79LsWlgVeJynwgWsIznEL0NokC5iDqJA9wWouFnZISSoLeVw==
-----END PUBLIC KEY-----

'''

print(nodes[0][-1]['Txs'][0]['owner_vk'].to_pem())
'''
假設執行緒數量對應算力成立的話
的確算力多的那一方決定哪個區塊被塞入區塊鏈
-----BEGIN PUBLIC KEY-----
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEbDNA4hzQN7iTbnHXvXaHsAxBk9AAOgfd
5j5/KF7dwVK7NsaMSLl1V7EYPWSvGr2P84pGT6UNFTYSLVKodeI+KA==
-----END PUBLIC KEY-----


'''
    

用執行緒多寡當作算力還蠻不嚴謹的，不過沒有意外計算小華交易的算力會較多，終究是成功交易了，可以從上面code中看到算力多的一方決定了哪些交易被加進區塊當中。

在github放有完整的範例程式提供，可以直接執行參考。

到目前為止的內容大致可以交叉參考這部影片:

接下來再把它放到網路上跑就勉強可以說實現了一個區塊鏈網路了，當然距離能實際應用的區塊鏈技術差了十萬八千里，只能算是驗證比特幣論文的概念而已，像我剛才想到key應該要轉string在去做hash會比較完整，雖然現在在同一隻程式裡跑沒有問題啦，現學現賣不斷更已經是我的極限了。

相關參考資源:

《Bitcoin: A Peer-to-Peer Electronic Cash System》
https://bitcoin.org/bitcoin.pdf
Blockchain Demo
https://anders.com/blockchain/